package LC;

/**
 * https://leetcode.com/problems/kth-largest-element-in-an-array/description/
 * Find the kth largest element in an unsorted array.
 * Note that it is the kth largest element in the sorted order, not the kth distinct element.
 * For example,
 * Given [3,2,1,5,6,4] and k = 2, return 5.
 * Note:
 * You may assume k is always valid, 1 ≤ k ≤ array's length.
 * Credits:
 * Special thanks to @mithmatt for adding this problem and creating all test cases.
 */
public class LC_215_KthLargestElementinanArray_Array_TwoPointers_BinarySearch {

    public static void main(String[] args) {
        int[] a = {3, 2, 1, 5, 6, 4};
        int k = 2;
        System.out.println(Solution.findKthLargest(a, k));
    }

    static class Solution {
        static int findKthLargest(int[] nums, int k) {
            if (k < 1 || nums == null || nums.length < k) throw new IllegalArgumentException();
            return findKthLargest(nums, 0, nums.length - 1, k);
        }

        static int findKthLargest(int[] nums, int start, int end, int k) {
            int pivot = nums[start];
            int lo = start;
            int hi = end;
            while (lo < hi) {
                while (lo < hi && nums[hi] >= pivot) hi--;
                nums[lo] = nums[hi];
                while (lo < hi && nums[lo] <= pivot) lo++;
                nums[hi] = nums[lo];
            }
            nums[lo] = pivot;
            if (end - lo + 1 == k) return pivot;
            else if (end - lo + 1 > k) return findKthLargest(nums, lo + 1, end, k);
            else return findKthLargest(nums, start, lo - 1, k - (end - lo + 1));
        }
    }
}